Aufgabe: Schreiben Sie reguläre Ausdrücke für die folgenden Sprachen:

a) Die Menge aller Zeichenreihen aus Nullen und Einsen, die die Teilzeichenreihe 101 nicht enthalten.

b) Die Menge aller Zeichenreihen mit der gleichen Anzahl Einsen und Nullen, die so geformt sind, dass jedes Präfix weder zwei Einsen mehr als Nullen, noch zwei Nullen mehr als Einsen hat

c) Die Menge aller Zeichenreihen aus Nullen und Einsen, deren Anzahl von Nullen durch 5 teilbar ist, und deren Anzahl von Einsen gerade.

Lösung:

a) 0^{∗}1^{∗}(1000^{∗}1)^{∗}1^{∗}0^{∗}

b) Die Zeichen reihen müssen die selbe Anzahl Nullen und Einsen haben. Kein Präfix darf zwei Nullen mehr als Einsen oder andersherum haben. Das bedeutet: Hat das Wort ω die Form a_{1}a_{2}a_{3}...a_{k}...a_{n}. Dann darf keine Teilzeichenreihe a_{1}a_{2}a_{3}...a_{k} für a ∈ {1, 2, ..., n} zwei Einsen mehr als Nullen oder zwei Nullen mehr als Einsen enthalten, also keine Teilzeichenreihe ...1000..., ...0100... o.ä. bzw. ...0111..., ...1011... o.ä.. Audrücke die Teilzeichenreihen der Form ...111... oder ...000... "auslösen" haben ja meist eine ähnliche Form wie ...1^{∗}... oder ...0^{∗}.... Um also längere Teilfolgen von Einsen oder Nullen zu verhindern paart man gleich von Anfang an Nullen und Einsen (01)^{∗}. Dieser Ausdruck würde alle Zeichenreihen der Form ...010101010101.... beschreiben. Das ist schon nah an der Lösung, da es alle Kriterien erfüllt: Selbe Anzahl Nullen und Einsen, und in keinem Präfix sind 2 mehr Nullen als Einsen oder anders herum. Jedoch gibt es ein groSSe Menge Zeichenreihen, die diese Kriterien erfüllen, die mit diesem Ausdruck aber nicht beschrieben sind, nämlich solche der Form ...010101...10...01001010.... Betrachtet man diese Zeichenreihe, stellt man fest, dass selbst wenn beliebig oft 10 in der Zeichenreihe auftritt, immernoch alle Kriterien erfüllt sind. Und damit hätte man dann auch noch den Teil gefunden, der die restlichen fehlenden Zeichenreihen beschreibt. Zusammen ergibt das dann: ((01) + (10))^{∗}